package com.kevin.Code.BinarySearch;

/**
 * @author Vinlee Xiao
 * @Classname SearchinRotatedSortedArray
 * @Description Leetcode 33. 搜索旋转排序数组 中等难度 二刷 提供更多种刷题思路
 * @Date 2022/2/25 16:40
 * @Version 1.0
 */
public class SearchinRotatedSortedArray {

    /**
     * 一刷思路
     *
     * @param nums
     * @param target
     * @return
     */
    public int search1(int[] nums, int target) {

        int len = nums.length;
        if (len == 1 && nums[0] == target) {
            return 0;
        }

        //找到开始旋转的坐标
        int index = 0;
        for (int i = 1; i < len; i++) {
            if (nums[i - 1] == target) {
                return i - 1;
            }

            if (nums[i] < nums[i - 1]) {
                index = i;
                break;
            }
        }

        //再使用二分查找
        int low = index;
        int high = len - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] > target) {
                high = mid - 1;
            }
            if (nums[mid] < target) {
                low = mid + 1;
            }

        }


        return -1;
    }

    /**
     * 思路很简单
     *
     * @param nums
     * @param target
     * @return
     */
    public int search2(int[] nums, int target) {
        int index = binarySearch2(nums, target);
        return index;
    }

    /**
     * 二刷思路 思路更好
     *
     * @param nums
     * @param target
     * @return
     */
    public int binarySearch2(int[] nums, int target) {


        if (nums.length == 1) {
            return nums[0] == target ? 0 : -1;
        }

        int low = 0;
        int high = nums.length - 1;

        while (low <= high) {
            int mid = (low + high) >> 1;
            if (nums[mid] == target) {
                return mid;
            }

            if (nums[0] <= nums[mid]) {
                if (nums[0] <= target && target < nums[mid]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[nums.length - 1]) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }

            }


        }

        return -1;
    }
}
